package algorithm_demo.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * <a href="https://leetcode.cn/problems/generate-parentheses/">https://leetcode.cn/problems/generate-parentheses/</a>
 * @author Api
 * @date 2023/4/29 15:03
 */
public class Problem_022_GenerateParentheses {
    public static List<String> generateParenthesis(int n) {
        char[] path = new char[n<<1];
        List<String> ans = new ArrayList<>();
        process(path, 0, 0, n, ans);
        return ans;
    }

    /**
     *
     * @param path 依次在path上填写决定
     * @param index ( ( ) ) ( ) ...
     *              0 1 2 3 4 5
     * @param leftMinusRight 左括号的数量-右括号的数量
     * @param leftRest 还可以填写左括号的数量
     * @param ans
     */
    public static void process(char[] path, int index, int leftMinusRight, int leftRest, List<String> ans){
        if (index == path.length){
            ans.add(String.valueOf(path));
        }else{
            if (leftRest > 0){
                path[index] = '(';
                process(path, index +1, leftMinusRight+1, leftRest-1, ans);
            }
            if (leftMinusRight > 0){
                path[index] = ')';
                process(path, index + 1, leftMinusRight-1, leftRest, ans);
            }
        }
    }

    public static void main(String[] args) {
        List<String> stringList = generateParenthesis(3);
        System.out.println(stringList.toString());
    }
}
